/*
 * @lc app=leetcode.cn id=429 lang=cpp
 *
 * [429] N 叉树的层序遍历
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution
{

    typedef struct
    {
        Node *node;
        int deep;
    } Cell;

public:
    vector<vector<int>> levelOrder(Node *root)
    {
        vector<vector<int>> ans;
        if (root == nullptr)
        {
            return ans;
        }
        queue<Cell> que;
        que.push(Cell{root, 0});
        while (!que.empty())
        {
            Cell curr = que.front();
            que.pop();
            if (ans.size() == curr.deep)
            {
                ans.push_back(vector<int>());
            }
            ans[curr.deep].push_back(curr.node->val);
            for (auto child : curr.node->children)
            {
                que.push(Cell{child, curr.deep + 1});
            }
        }
        return ans;
    }
};
// @lc code=end
